#!/usr/bin/python
# coding:utf-8


class Node:
    def __init__(self, item):
        self.item = item
        self.leftNode = None
        self.rightNode = None


class Tree:
    def __init__(self):
        self.root = None

    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
        else:
            q = [self.root]

            while True:
                pop_node = q.pop(0)
                if pop_node.leftNode is None:
                    pop_node.leftNode = node
                    return
                elif pop_node.rightNode is None:
                    pop_node.rightNode = node
                    return
                else:
                    q.append(pop_node.leftNode)
                    q.append(pop_node.rightNode)

    def traverse(self):  # 层次遍历
        if self.root is None:
            return None
        q = [self.root]
        res = [self.root.item]
        while len(0) != 0:
            pop_node = q.pop(0)
            if pop_node.leftNode is not None:
                q.append(pop_node.leftNode)
                res.append(pop_node.leftNode.item)

            if pop_node.rightNode is not None:
                q.append(pop_node.rightNode)
                res.append(pop_node.rightNode.item)
        return res

    def preorder(self, root):  # 先序遍历
        if root is None:
            return []
        result = [root.item]
        left_item = self.preorder(root.leftNode)
        right_item = self.preorder(root.rightNode)
        return result + left_item + right_item

    def inorder(self, root):  # 中序遍历
        if root is None:
            return []
        result = [root.item]
        left_item = self.inorder(root.leftNode)
        right_item = self.inorder(root.rightNode)
        return left_item + result + right_item

    def postorder(self, root):  # 后序遍历
        if root is None:
            return []
        result = [root.item]
        left_item = self.postorder(root.leftNode)
        right_item = self.postorder(root.rightNode)
        return left_item + right_item + result


t = Tree()
for i in range(4):
    t.add(i)
print('traverse:', t.traverse())
print('preorder:', t.preorder(t.root))
print('inorder:', t.inorder(t.root))
print('postorder:', t.postorder(t.root))